# !/usr/bin/env python
# -*- coding: utf-8 -*-
"""
@Time        : 2021/3/7 14:40
@Author      : Albert Darren
@Contact     : 2563491540@qq.com
@File        : LocalHighPoints.py
@Version     : Version 1.0.0
@Description : TODO 面向数组实现局部最高点算法
@Created By  : PyCharm
"""
import numpy as np
import timeit


def get_input():
    latitude_array = np.array([], dtype=np.float64)
    while 1:
        latitude = input("请输入海拔高度或者按enter键退出:")
        if latitude == "":
            break
        latitude_array = np.append(latitude_array, eval(latitude))
    return latitude_array


def linear_search_lhp(height_array: np.ndarray):
    """
    实现时间复杂度T(n)=O(n)的第一种算法
    :param height_array: 海拔高度数组
    :return: 寻找局部高点结果
    """
    is_exist = False
    height_array = np.insert(height_array, 0, -np.inf)
    height_array = np.append(height_array, -np.inf)  # 在海拔数组左右两端加上负无穷-oo
    search_count = 0
    for i in range(1, len(height_array) - 1):
        search_count += 1
        if height_array[i - 1] <= height_array[i] >= height_array[i + 1]:
            is_exist = True
            break
    return is_exist, search_count


def log_search_lhp(height_array: np.ndarray):
    """
    实现时间复杂度T(n)=O(log n)的第二种算法
    :param height_array: 海拔高度数组
    :return: 寻找局部高点结果
    """
    is_exist = False
    search_count = 0  # 查找 次数
    left_index = len(height_array) - 1
    right_index = 0
    medium_index = 0
    while not is_exist:  # 找到局部高点结束
        medium_index = int((right_index + left_index) / 2)
        if left_index != right_index:
            if height_array[medium_index] < height_array[medium_index + 1]:
                right_index = medium_index + 1
            elif height_array[medium_index] < height_array[medium_index - 1]:
                left_index = medium_index - 1
            else:
                is_exist = True
        else:
            is_exist = True
        search_count += 1
    return is_exist, search_count, medium_index


if __name__ == '__main__':
    latitude_values = np.array([1, 2, 6, 5, 3, 7, 4], dtype=np.float64)  # get_input()
    # 详见程振波算法设计与分析(Python),P11 e.g 1-3-b
    is_find = linear_search_lhp(latitude_values)
    print("局部高点{}".format("存在" if is_find else "不存在"))

    # 详见程振波算法设计与分析(Python),P11 e.g 1-3-c
    is_search = log_search_lhp(latitude_values)
    print("局部高点{}".format("存在" if is_search else "不存在"))

    # # 详见程振波算法设计与分析(Python),P11 e.g 1-3-d
    # high_points_array = np.random.uniform(-1000, 1000, size=(10000000,))
    # linear_search_time = timeit.Timer("linear_search_lhp(random_array)",
    #                                   "from __main__ import linear_search_lhp,random_array")
    # print("复杂度为O(n)的算法在机器上运行时间为:{}".format(linear_search_time.timeit(10)))
    #
    # # 详见程振波算法设计与分析(Python),P11 e.g 1-3-e
    # log_search_time = timeit.Timer("log_search_lhp(random_array)",
    #                                "from __main__ import log_search_lhp,random_array")
    # print("复杂度为O(log n)的算法在机器上运行时间为:{}".format(log_search_time.timeit(10)))

    # 详见程振波算法设计与分析(Python),P11 e.g 1-3-d
    high_points_array = np.zeros(shape=(10000000,))
    high_points_array[-2] = 1
    linear_search_time = timeit.Timer("linear_search_lhp(high_points_array)",
                                      "from __main__ import linear_search_lhp,high_points_array")
    print("复杂度为O(n)的算法在机器上运行时间为:{}".format(linear_search_time.timeit(10)))

    # 详见程振波算法设计与分析(Python),P11 e.g 1-3-e
    log_search_time = timeit.Timer("log_search_lhp(high_points_array)",
                                   "from __main__ import log_search_lhp,high_points_array")
    print("复杂度为O(log n)的算法在机器上运行时间为:{}".format(log_search_time.timeit(10)))
